#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 5005;

int n, m;
struct Node {
  int v, c;
};
vector<Node> a, b, c;
int dpa[N], dpb[N], dpc[N];
void solve(const vector<Node>& a, int dp[N]) {
  // packback : the maximum v
  for (Node x : a) {
    per(j, m, x.c) { dp[j] = max(dp[j], dp[j - x.c] + x.v); }
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) {
    int x, y, z;
    cin >> x >> y >> z;
    if (x == 1)
      a.push_back(Node{y, z});
    else if (x == 2)
      b.push_back(Node{y, z});
    else
      c.push_back(Node{y, z});
  }
  solve(a, dpa);
  solve(b, dpb);
  solve(c, dpc);
  int l = 1, r = min({dpa[m], dpb[m], dpc[m]});
  while (l <= r) {
    int mid = (l + r) >> 1;
    int x = lower_bound(dpa + 1, dpa + m + 1, mid) - dpa;
    int y = lower_bound(dpb + 1, dpb + m + 1, mid) - dpb;
    int z = lower_bound(dpc + 1, dpc + m + 1, mid) - dpc;
    if (x + y + z <= m)
      l = mid + 1;
    else
      r = mid - 1;
  }
  cout << r;
  return 0;
}